package com.cx.algrithm.binary_tree.binary_search_tree.red_black_tree;

import java.util.Scanner;

/**
 * @Author: robert.song
 * @Date: Created in 2021/10/18
 */
class RBTree<K extends Comparable<K>, V> {

    private static final boolean RED = false;
    private static final boolean BLACK = true;
    //  红黑树的root节点
    private static RBNode root;

//    public static void main(String[] args) {
//        Scanner scan = new Scanner(System.in);
//        String[] strs = scan.nextLine().split(",");
//        RBTree rbTree = new RBTree();
//        for(int i = 0; i<strs.length; i++){
//            rbTree.put(i,strs[i]);
//        }
//        traverse(root);
//        scan.close();
//    }

    public static RBNode getRoot() {
        return root;
    }

    public static void setRoot(RBNode root) {
        RBTree.root = root;
    }

    /**
     * 实现左旋
     * p           pr
     * /\           /\
     * pl pr  ==>   p  rr
     * /\       /\
     * rl rr    pl rl
     * 左旋：
     * p-pl 和 pr-rr的关系不需要调整
     * 需要调整的情况
     * 1. pr-rl 调整为 p-rl
     * 将rl变成p的右子结点
     * 将p设置为rl的父节点
     * 2. 判断p是否有父节点
     * 如果有
     * pr.parent = p.parent
     * pr为p.parent的子节点，到底是左子节点还是右子节点？
     * if p.parent.left == p
     * p.parent.left = pr
     * else
     * p.parent.right = pr
     * <p>
     * 如果没有
     * 直接把pr设置为root节点
     * 3. 最后p和pr交换
     * p.parent = pr
     * pr.left = p
     *
     * @param p
     */
    private void leftRotate(RBNode p) {
        if (p != null) {
//            获取到了pr节点
            RBNode pr = p.right;
//            1：pr-rl 调整为 p-rl
            p.right = pr.left;
            if (pr.left != null) {
                pr.left.parent = p;
            }
//            2：判断p节点是否有父节点
            pr.parent = p.parent;
            if (p.parent == null) {
//                说明p无父节点，本身就是root节点，这时候pr会变成新root节点
                root = pr;
            }
//                如果p有父节点
            else if (p.parent.left == p) {
//                如果p是父节点的左子节点，那么pr肯定是p的父节点的左子节点
                p.parent.left = pr;
            } else {
                p.parent.right = pr;
            }
//            3： 设置p为pr左子节点
            pr.left = p;
            p.parent = pr;
        }
    }

    /**
     * 实现左旋
     * 逻辑同左旋.
     *
     * @param p
     */
    private void rightRotate(RBNode p) {
        if (p != null) {
//            获取到了pr节点
            RBNode pr = p.left;
//            1：pr-rl 调整为 p-rl
            p.left = pr.right;
            if (pr.right != null) {
                pr.right.parent = p;
            }
//            2：判断p节点是否有父节点
            pr.parent = p.parent;
            if (p.parent == null) {
//                说明p无父节点，本身就是root节点，这时候pr会变成新root节点
                root = pr;
            }
//                如果p有父节点
            else if (p.parent.right == p) {
//                如果p是父节点的左子节点，那么pr肯定是p的父节点的左子节点
                p.parent.right = pr;
            } else {
                p.parent.left = pr;
            }
//            3： 设置p为pr左子节点
            pr.right = p;
            p.parent = pr;
        }
    }

    /**
     * 红黑树 新增节点
     *
     * @param key
     * @param value
     */
    public void put(K key, V value) {
        RBNode t = root;
        if (t == null) {
//            这是插入的第一个节点
            root = new RBNode(null, key, value == null ? key : value);
            return;
        }
        int cmp;
//        1.找到插入的位置(找到新增节点的父节点)
        RBNode parent;
        do {
            parent = t;
            cmp = (key.compareTo((K) t.key));
            if (cmp < 0) {
//                从左侧查找
                t = t.left;
            } else if (cmp > 0) {
//                从右侧查找
                t = t.right;
            } else {
//                说明节点存在，用插入节点的值覆盖掉相同的节点
                t.setValue(value == null ? key : value);
                return;
            }

        } while (t != null);
//        2.将新节点添加到父节点的子节点中（左右子节点）
//        创建要插入的节点
        RBNode node = new RBNode(key, value == null ? key : value, parent);
        if (cmp < 0) {
//            将新节点添加到父节点左侧
            parent.left = node;
        } else {
//            添加到右侧
            parent.right = node;
        }
//        旋转和变色
        fixAfterPut(node);

    }

    public void remove(V key) {
    }

    private RBNode parentOf(RBNode node) {
        return node != null ? node.parent : null;
    }

    private RBNode leftOf(RBNode node) {
        return node != null ? node.left : null;
    }


    private RBNode rightOf(RBNode node) {
        return node != null ? node.right : null;
    }

    private boolean colorOf(RBNode node) {
        return node == null ? BLACK : node.color;
    }

    private void setColor(RBNode node, boolean color) {
        if (node != null) {
            node.setColor(color);
        }
    }

    /**
     * 插入节点操作
     * 2-3-4对应的操作
     * 2节点：新插入一个元素 直接和2节点合并 不用调整
     * 红黑树：新增一个红色节点在黑色节点下 不需要调整
     * 3节点：新插入一个元素在3节点下 那么会出现6种情况（2种不需要调整，4种需要调整）
     * 红黑树：插入的节点是插入在上黑下红结构中的红色节点
     * 例如：
     * N1(黑色，已有节点)
     * /          \
     * N2(红色，已有节点)   N3(红色，已有节点)
     * /
     * N4(红色，新增节点)
     * 4节点：新插入一个元素在4节点下，那么会出现4中情况 都需要调整
     * 红黑树：新增的节点是红色 爷爷节点是黑色，父节点是红色
     *
     * @param x
     */
    private void fixAfterPut(RBNode<K, Object> x) {
//        插入的节点 肯定红色
        x.color = RED;
//        2节点不用调整，3，4节点需要调整
        while (x != null && x != root && x.parent.color == RED) {
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//            需要调整的只剩下4种情况，有叔叔节点和没有叔叔节点
//            获取插入节点的叔叔节点
                RBNode y = rightOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
//                说明有叔叔节点
//                变色+递归
//                父亲和叔叔变为黑色，爷爷边红色
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
//                递归处理
                    x = parentOf(parentOf(x));
                } else {
//                说明没有叔叔节点
                    if (x == parentOf(x).right) {
                        x = parentOf(x);
                        leftOf(x);
                    }
//                父节点变为黑色 爷爷节点变为红色
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
//                根据爷爷节点右旋
                    rightRotate(parentOf(parentOf(x)));
                }
            } else {
//            和上面情况刚好相反，又是四种情况
//                获取插入节点的叔叔节点
                RBNode y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
//                说明有叔叔节点
//                变色+递归
//                父亲和叔叔变为黑色，爷爷边红色
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
//                递归处理
                    x = parentOf(parentOf(x));
                } else {
//                说明没有叔叔节点
                    if (x == parentOf(x).right) {
                        x = parentOf(x);
                        leftOf(x);
                    }
//                父节点变为黑色 爷爷节点变为红色
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
//                根据爷爷节点左旋
                    leftRotate(parentOf(parentOf(x)));
                }
            }

        }
    }

    static class RBNode<K extends Comparable<K>, V> {
        private RBNode parent;
        private RBNode left;
        private RBNode right;
        private boolean color;
        private K key;
        private V value;

        public RBNode() {
        }

        public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, K key, V value) {
            this.parent = parent;
            this.left = left;
            this.right = right;
            this.color = color;
            this.key = key;
            this.value = value;
        }

        public RBNode(K k, V v, RBNode parent) {
            this.key = k;
            this.value = v;
            this.parent = parent;
        }

        public RBNode getParent() {
            return parent;
        }

        public void setParent(RBNode parent) {
            this.parent = parent;
        }

        public RBNode getLeft() {
            return left;
        }

        public void setLeft(RBNode left) {
            this.left = left;
        }

        public RBNode getRight() {
            return right;
        }

        public void setRight(RBNode right) {
            this.right = right;
        }

        public boolean isColor() {
            return color;
        }

        public void setColor(boolean color) {
            this.color = color;
        }

        public K getKey() {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }

        public RBNode(RBNode parent, K key, V value) {
            this.parent = parent;
            this.key = key;
            this.value = value;
        }
    }

}
